import java.awt.Point;
import java.util.ArrayList;
import java.util.Random;

/**
 * The class maintain two dimensional array data-structure of PuzzleCell. It contains 
 * various functions to efficiently store and manipulate various words in various positions 
 * to create effective puzzles. 
 * 
 * @Function_prototypes:
 * public void clear()  
 * public boolean isEmpty (int x, int y)       
 * public int getWidth()
 * public int getHeight()
 * public void setWidth(int newWidth)
 * public void setHeight(int newHeight)
 * public void setDimensions(int newWidth, int newHeight)
 * public char getChar(int x, int y)
 * public int getWordCount(int x, int y)
 * public void addWord (String word, Point[] location)
 * public void deleteWord (String word, Point[] location) 
 * public void setChar(int x, int y, char letter) 
 * public boolean removeChar(int x, int y, char letter) 
 * public void removeChar(int x, int y)
 * public Point getUp(int x, int y) 
 * public Point getDown(int x, int y) 
 * public Point getLeft(int x, int y)  
 * public Point getRight(int x, int y)
 * public Point getUpLeft(int x, int y) 
 * public Point getUpRight(int x, int y)  
 * public Point getDownLeft(int x, int y) 
 * public Point getDownRight(int x, int y)
 * public void fillRandom(char[] chars) 
 * public ArrayList<Point[]> locationInPuzzle(String word)
 * public Point[] findWordLocationAt (int x, int y, String word)
 * private ArrayList<Point[]> searchAt(String word, int r, int c) 
 * private boolean searchThisWay(String word, int r, int c, int dR, int dC)
 * private Point[] getLocation(String word, int r, int c, int dR, int dC)
 * public void saveState()
 * public boolean popPreState() 
 * private PuzzleBoard stateSnapShot() 
 *   
 * 
 * @author Hardik
 * @see PuzzleCell, Point, ArrayList<E>, 
 */
public class PuzzleBoard implements Cloneable {

	private  ArrayList<PuzzleCell[][]> puzzleStack;
	private PuzzleCell[][] puzzleBoard;
	private int width;
	private int height;


	/**
	 * Initialize PuzzleBoard object with width and height to given 
	 * in parameters in order.   
	 * 
	 * @param initialWidth
	 * @param initialHeight
	 */
	public PuzzleBoard (int initialWidth, int initialHeight) {
		// TODO Auto-generated constructor stub
		width = initialWidth;
		height = initialHeight;
		puzzleBoard = new PuzzleCell[width][height];

		for (int i = 0; i < width; i++) {
			for (int j = 0; j < height; j++) {
				puzzleBoard[i][j] = new PuzzleCell (' '); 
			}
		}
	}

	/**
	 * A function clears the puzzleBoard and assigned a new empty board of the same 
	 * size 
	 */
	public void clear() {
		puzzleBoard = new PuzzleCell[width][height];
	}
	
	/**
	 * A function tells whether puzzleCell at given coordinates of puzzleBoard is 
	 * empty or not 
	 * 
	 * @param x coordinate of puzzleCell object
	 * @param y coordinate of puzzleCell object
	 * @return boolean value indicating whether puzzleCell is null or not
	 */
	public boolean isEmpty (int x, int y) {
		return ((puzzleBoard[x][y] == null)); 
	}
	
	/**
	 * A function provides the width (number of columns) of the PuzzleBoard
	 * 
	 * @return width of PuzzleBoard obj in integer value
	 */
	public int getWidth() {
		return (width);
	}
	
	/**
	 * A function provides the height (number of rows) of the PuzzleBoard
	 * 
	 * @return height of PuzzleBoard obj in integer value
	 */
	public int getHeight() {
		return (height);
	}
	
	/**
	 * A function sets the width of the PuzzleBoard object 
	 * 
	 * @param newWidth, in integer, to reset width of PuzzleBoard obj
	 */
	public void setWidth(int newWidth) {
		setDimensions(newWidth, height);
	}
	
	/**
	 * A function sets the height of the PuzzleBoard object 
	 * 
	 * @param newHeight, in integer, to reset height of PuzzleBoard obj
	 */
	public void setHeight(int newHeight) {
		setDimensions(width, newHeight);
	}

    
	/**
	 * A function sets the dimensions (width and height) of the PuzzleBoard object
	 * 
	 * @param newWidth, in integer, to reset width of PuzzleBoard obj
	 * @param newHeight, in integer, to reset height of PuzzleBoard obj
	 */
	public void setDimensions(int newWidth, int newHeight) {
		if (height == newHeight && width == newWidth) { // if newDimensions are same as old one
			return; 
		}
		height = newHeight;
		width = newWidth;
		PuzzleCell[][] newBoard = new PuzzleCell[height][width];

		int heightCopy;
		int widthCopy;

		if (newBoard[0].length >= puzzleBoard[0].length) {// newHeight >= height
			heightCopy = puzzleBoard[0].length;
		} else {// newHeight < height
			heightCopy = newBoard[0].length;
		}

		if (newBoard.length >= puzzleBoard.length) {// newWidth >= width
			widthCopy = puzzleBoard.length;
		} else { // newWidth < width
			widthCopy = newBoard.length;
		}

		for (int x = 0; x < widthCopy; x++) {
			System.arraycopy(puzzleBoard[x], 0, newBoard[x], 0, heightCopy);
		}
		puzzleBoard = newBoard; 
	}
	
	/**
	 * A function provides the character held by PuzzleCell at given location 
	 * of PuzzleBoard object
	 * 
	 * @param int x coordinate of character location 
	 * @param int y coordinate of character location 
	 * 
	 * @return character held by PuzzleCell at given location of PuzzleBoard object 
	 */
	public char getChar(int x, int y) {
		return (puzzleBoard[x][y].getChar());
	}
	
	/**
	 * A function provides the count, number of words that intersect the given PuzzleCell, 
	 * as integer value
	 * 
	 * @param int x coordinate of character location 
	 * @param int y coordinate of character location 
	 * 
	 * @return integer value count - number of words that intersect the given PuzzleCell 
	 */
	public int getWordCount(int x, int y) {
		return (puzzleBoard[x][y].getCount());
	}

    /**
     * A function adds word in puzzleBoard at specified location in the puzzleBoard
     * 
     * @param word to add into puzzleBoard
     * @param location of the word in puzzleBoard
     */
	public void addWord (String word, Point[] location) { 
    	 for (int i = 0; i < location.length; i++ ){
    		 int x = location[i].x;
    		 int y = location[i].y;
    		 char letter = word.charAt(i); 
    		 setChar(x,y,letter); 
    	 }
     }
	
	/**
     * A function deletes word from the puzzleBoard at specified location in the puzzleBoard
     * 
     * @param word to delete from the puzzleBoard
     * @param location of the word in puzzleBoard
     */
	public void deleteWord (String word, Point[] location) { 
    	 for (int i = 0; i < location.length; i++ ){
    		 int x = location[i].x;
    		 int y = location[i].y;
    		 char letter = word.charAt(i); 
    		 removeChar(x,y,letter); 
    	 }
     }
	
	/**
	 * A function inserts a letter into PuzzleBoard object at given coordinates 
	 * 
	 * @param int x coordinate of insertion location
	 * @param int y coordinate of insertion location
	 * @param letter to insert
	 */
	public void setChar(int x, int y, char letter) {
		PuzzleCell puzzleCell = new PuzzleCell(letter);
        
		// if PuzzleCell is empty or contain different letter 
		if (puzzleBoard[x][y] == null || puzzleBoard[x][y].getChar() != letter) {
			puzzleBoard[x][y] = puzzleCell;
		}
		puzzleBoard[x][y].countUp();
	}

	/**
	 * A function removes given letter from PuzzleBoard object at given coordinates
	 * 
	 * @param int x coordinate of removal location
	 * @param int y coordinate of removal location
	 * @param letter to remove
	 * 
	 * @return boolean values - whether letter is removed or not
	 */
	public boolean removeChar(int x, int y, char letter) {

		// if PuzzleCell contain the given letter  
		if (puzzleBoard[x][y].getChar() == letter) {
			// if the letter intersect only one word
			if (puzzleBoard[x][y].getCount() == 1) {
				puzzleBoard[x][y] = new PuzzleCell (' ');
			}
			puzzleBoard[x][y].countDown();
			return (true);
		}
		return false; // if PuzzleCell doesn't contain the given letter
	}

	/**
	 * A function removes any character from PuzzleBoard object at given coordinates
	 * 
	 * @param int x coordinate of character location to remove
	 * @param int y coordinate of character location to remove
	 */
	public void removeChar(int x, int y) {
		puzzleBoard[x][y] = new PuzzleCell (' ');
	}

	/**
	 * A function provides location of any direction in puzzleBoard if there is 
	 * for given location coordinates in given direction otherwise give current location 
	 *  
	 * @param x coordinate of current position
	 * @param y coordinate of current position
	 * @param direction as in string, such as "N", "S", "NW" or "NE". 
	 *        It's case insensitive  
	 * 
	 * @return requested position - location coordinate in Point obj
	 */
	public Point getPosition(int x, int y, String direction) {
		Point position = null;
		direction = direction.toUpperCase(); 
		
		if (direction == "N"){ 
			position = getUp(x, y); 
		} else if (direction == "S"){ 
			position = getDown(x, y);
		} else if (direction == "E"){ 
			position = getRight(x, y);
		} else if (direction == "W"){
			position = getLeft(x, y); 	
		} else if (direction == "NE"){ 
			position = getUpRight(x, y);
		} else  if (direction == "NW"){
			position = getUpLeft(x, y);
		} else if (direction == "SE"){ 
			position = getDownLeft(x, y);
		} else if (direction == "SW"){ 
			position = getDownRight(x,y);
		} 
		
		return (position); 
	}
	
	/**
	 * A function provides location above if there is for given location coordinates 
	 * otherwise give location (-1, -1) with coordinates
	 * 
	 * @param int x coordinate of current location
	 * @param int y coordinate of current location
	 * 
	 * @return up - location coordinate in Point obj
	 */
	public Point getUp(int x, int y) {
		Point up;
		if (y >= 0) {
			up = new Point(x, --y);
			return (up);
		}
		up = new Point(-1, -1);
		return (up);
	}

	/**
	 * A function provides location bellow if there is for given location coordinates 
	 * otherwise give location (-1, -1) with coordinates
	 * 
	 * @param int x coordinate of current location
	 * @param int y coordinate of current location
	 * 
	 * @return down - location coordinate in Point obj
	 */
	public Point getDown(int x, int y) {
		Point down;
		if (y <= (height - 1)) {
			down = new Point(x, ++y);
			return (down);
		}
		down = new Point(-1, -1);
		return (down);
	}

	/**
	 * A function provides location of one left if there is for given location coordinates 
	 * otherwise give location (-1, -1) with coordinates
	 * 
	 * @param int x coordinate of current location
	 * @param int y coordinate of current location
	 * 
	 * @return left - location coordinate in Point obj
	 */
	public Point getLeft(int x, int y) {
		Point left;
		if (x >= 0) {
			left = new Point(--x, y);
			return (left);
		}
		left = new Point(-1, -1);
		return (left);
	}

	/**
	 * A function provides location of one right if there is for given location coordinates 
	 * otherwise give location (-1, -1) with coordinates
	 * 
	 * @param int x coordinate of current location
	 * @param int y coordinate of current location
	 * 
	 * @return right - location coordinate in Point obj
	 */
	public Point getRight(int x, int y) {
		Point right;
		if (x <= (width - 1)) {
			right = new Point(++x, y);
			return (right);
		}
		right = new Point(-1, -1);
		return (right);
	}

	/**
	 * A function provides north-east location point if there is for given location 
	 * coordinates otherwise give location (-1, -1) with coordinates
	 * 
	 * @param int x coordinate of current location
	 * @param int y coordinate of current location
	 * 
	 * @return upLeft - location coordinate in Point obj
	 */
	public Point getUpLeft(int x, int y) {
		Point upLeft;
		if (x >= 0 && y >= 0) {
			upLeft = new Point(--x, --y);
			return (upLeft);
		}
		upLeft = new Point(-1, -1);
		return (upLeft);
	}

	/**
	 * A function provides north-west location point if there is for given 
	 * location coordinates otherwise give location (-1, -1) with coordinates
	 * 
	 * @param int x coordinate of current location
	 * @param int y coordinate of current location
	 * 
	 * @return upRight - location coordinate in Point obj
	 */
	public Point getUpRight(int x, int y) {
		Point upRight;
		if (x <= (width - 1) && y >= 0) {
			upRight = new Point(++x, --y);
			return (upRight);
		}
		upRight = new Point(-1, -1);
		return (upRight);
	}

	/**
	 * A function provides south-east location point if there is for given 
	 * location coordinates otherwise give location (-1, -1) with coordinates
	 * 
	 * @param int x coordinate of current location
	 * @param int y coordinate of current location
	 * 
	 * @return downLeft - location coordinate in Point obj
	 */
	public Point getDownLeft(int x, int y) {
		Point downLeft;
		if (x >= 0 && y <= (height - 1)) {
			downLeft = new Point(--x, ++y);
			return (downLeft);
		}
		downLeft = new Point(-1, -1);
		return (downLeft);
	}

	/**
	 * A function provides south-west location point if there is for given 
	 * location coordinates otherwise give location (-1, -1) with coordinates 
	 * 
	 * @param int x coordinate of current location
	 * @param int y coordinate of current location
	 * 
	 * @return downRight - location coordinate in Point obj
	 */
	public Point getDownRight(int x, int y) {
		Point downRight;
		if (x <= (width - 1) && y <= (height - 1)) {
			downRight = new Point(++x, ++y);
			return (downRight);
		}
		downRight = new Point(-1, -1);
		return (downRight);
	}

	/**
	 * A function fills surrounding of puzzles in PuzzleBoard with given 
	 * characters in random order
	 * 
	 * @param char[] chars - array of characters to fill in surrounding of
	 *        puzzles in PuzzleBaord
	 */
	public void fillRandom(char[] chars) {
		Random rand = new Random();

		for (int y = 0; y < puzzleBoard[0].length; y++) {
			for (int x = 0; x < puzzleBoard.length; x++) {
				if (puzzleBoard[x][y].getChar() == ' ') {
					char randChar = chars[rand.nextInt(chars.length)];
					PuzzleCell randCell = new PuzzleCell(randChar);
					puzzleBoard[x][y] = randCell;
				}
			}
		}
	}

	/**
	 * A function provides array of Point[] for given words location, 
	 * where Point[] is an array of points in order corresponding to letters of a word  
	 * 
	 * @author Beth Katz - modified by Hardik Patel
	 * 
	 * @param word - the word to search for
	 * 
	 * @return ArrayList <Point[]> wordFounds - array of Point[] of several
	 *         locations of given word in PuzzleBoard
	 */
	public ArrayList<Point[]> locationsInPuzzle(String word) {
		ArrayList<Point[]> wordFounds = new ArrayList<Point[]>();
		for (int i = 1; i <= width; i++) {
			for (int j = 1; j <= height; j++) {
				if (puzzleBoard[i][j].getChar() == word.charAt(0)) {
					wordFounds.addAll(searchAt(word, i, j));
				}
			}
		}
		return (wordFounds);
	}
	
	/**
	 * A function search for word in the puzzle at location x,y. 
	 * and provide array of Point for given words location, where Point[] 
	 * is an array of points in order corresponding to letters of a word
	 * 
	 * @param word - the word to search for
	 * @param x - the row location
	 * @param y - the column location
	 * 
	 * @return Point[] - array of Point of given word location in PuzzleBoard
	 */
	public Point[] findWordLocationAt (int x, int y, String word){ 
		return (searchAt(word, x, y).get(0)); 
	}
	
	/**
	 * A function search for word in the puzzle at location r,c. 
	 * and provide array of Point[] for given words location, where Point[] 
	 * is an array of points in order corresponding to letters of a word
	 * 
	 * @author Beth Katz - modified by Hardik Patel
	 * 
	 * @param word - the word to search for
	 * @param r - the row location
	 * @param c - the column location
	 * 
	 * @return ArrayList <Point[]> wordFounds - array of Point[] of several
	 *         locations of given word in PuzzleBoard
	 */
	private ArrayList<Point[]> searchAt(String word, int r, int c) {
		ArrayList<Point[]> wordFounds = new ArrayList<Point[]>();
		
		for (int dR = -1; dR <= 1; dR++) {
			for (int dC = -1; dC <= 1; dC++) {
				if (!((dR == 0) && (dC == 0))) { // not 0,0
					if (searchThisWay(word, r, c, dR, dC)) {
						wordFounds.add(getLocation(word, r, c, dR, dC));
					}
				}
			}
		}
		return (wordFounds);
	}

	/**
	 * A function search for word in the puzzle at location r,c going in dR,dC direction.
	 * and return boolean value to indicate whether given word is found or not
	 * 
	 * @author Beth Katz - modified by Hardik Patel
	 * 
	 * @param word - the word to search for
	 * @param r - the row location
	 * @param c - the column location
	 * @param dR - the row direction to search in
	 * @param dC - the column direction to search in
	 * 
	 * @return boolean value - indicating whether given word is in particular
	 *         direction or not
	 */
	private boolean searchThisWay(String word, int r, int c, int dR, int dC) {
		int w = 0; // index into word
		int row = r;
		int col = c;
		final char NULL = '\0';
		word = word + NULL;

		while (word.charAt(w) == puzzleBoard[row][col].getChar()) {
			row += dR;
			col += dC;
			w++;
		}
		if (word.charAt(w) == NULL) {
			return (true);
		}
		return (false);
	}

	/**
	 * A function provides the location of words as Point [], where Point[] 
	 * is an array of points in order corresponding to letters of a word   
	 * 
	 * @author Beth Katz - modified by Hardik Patel
	 * 
	 * @param word - String obj to find in PuzzleBoard
	 * @param r - x coordinate of first character of the given word as integer
	 * @param c - y coordinate of first character of the given word as integer
	 * @param dR - x coordinate of next char of word in particular direction
	 * @param dC - y coordinate of next char of word in particular direction
	 * 
	 * @return Point[] location - array of points in order of corresponding
	 *         letters in givan word
	 */
	private Point[] getLocation(String word, int r, int c, int dR, int dC) {
		Point[] location = new Point[word.length()];
		int w = 0; // index into word
		int row = r;
		int col = c;
		final char NULL = '\0';
		word = word + NULL;

		do {
			location[w] = new Point(row, col);
			row += dR;
			col += dC;
			w++;
		} while (word.charAt(w) == NULL);
		return (location);
	}
	
	/**
	 * A function save current state of puzzleBoard within itself
	 * 
	 */
	public void saveState() { 
		PuzzleCell[][] currentState = stateSnapShot(); 
		puzzleStack.add(currentState);
	}
		
	/**
	 * A function reset PuzzleBoard object to previous state of itself
	 * and remove previous state from stack. 
	 * If there is no previous state, return false value
	 * 
	 * @return boolean value indicating whether puzzleBoard set to 
	 *         previous state or not   
	 */
	public boolean popPreState() { 
		int lastIndex = puzzleStack.size()-1;
		PuzzleCell[][] preState = null; 
		if (lastIndex >= 0){
			preState = puzzleStack.get(lastIndex);
			puzzleBoard = preState;
			width = preState.length;
			height = preState[0].length;
			puzzleStack.remove(lastIndex);
			return (true); 
		}
		return (false); 
	}
	

    /**
     * A function gives snapshot copy of PuzzleBoard, with theBoard, width and height, 
     * but not the puzzleStack
     * 
     * @return puzzleBoardCopy - copy of puzzleBoard 
     */
	private PuzzleCell[][] stateSnapShot() {
		PuzzleCell[][] puzzleBoardCopy = new PuzzleCell [width] [height];   		
		// copy every puzzleCell of puzzleBoard  
		for (int x = 0; x < width; x++) {
			for (int y = 0; y < height; y++) {
				try {
					puzzleBoardCopy[x][y] = (PuzzleCell) puzzleBoard[x][y].clone();
				} catch (CloneNotSupportedException e) {
					puzzleBoardCopy[x][y] = new PuzzleCell (' ');
				}
			}
		}		
		return (puzzleBoardCopy); 
	}
}
